Python performance optimization

Membership testing is faster in dict than in list.

Python dictionaries use hash tables, this means that a lookup operation (e.g., if x in y) is O(1). A lookup operation in a list means that the entire list needs to be iterated, resulting in O(n) for a list of length n. http://www.clips.ua.ac.be/tutorials/python-performance-optimization


In [1]:
import timeit
def test_ifin(d):
    if 5000 in d:
        a = 1
    else:
        a = 2

d1 = dict.fromkeys(range(10000), True)
d2 = range(10000)

In [2]:
print (timeit.timeit(lambda: test_ifin(d1), number=1000))
print (timeit.timeit(lambda: test_ifin(d2), number=1000))


0.000880002975464
0.0672550201416

In [ ]: